#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    int tar = 0;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        tar = target;
        for (int i = 0; i < candidates.size(); ++i)
            dfs(candidates, {}, i, 0);

        return ret;
    }

    void dfs(vector<int>& candidates, vector<int> path, int pos, int sum)
    {
        if (pos == candidates.size())
        {
            return;
        }

        int tmp = candidates[pos];
        while (sum < tar)
        {
            sum += tmp;
            path.push_back(tmp);
            if (sum == tar)
            {
                ret.push_back(path);
                return;
            }
            if (sum > tar)
                return;

            for (int i = pos + 1; i < candidates.size(); ++i)
            {
                if (sum + candidates[pos] > tar)
                    return;
                dfs(candidates, path, i, sum);
            }
        }

        //dfs(candidates,{},pos + 1, 0);
    }
};